
// 416.分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 经典的01背包问题 , 每个数据只有选和不选两种情况
        int n = nums.size();
        int sum = accumulate(nums.begin() , nums.end() , 0 );
        if(sum % 2 == 1) return false;

        vector<bool> dp(sum/2 + 1);
        dp[0] = true;
        for(int i = 1 ;i <= n ;i++)
            for(int j = sum/2; j >= nums[i - 1] ; j--)
                if(dp[j - nums[i - 1]]) dp[j] = true;

        return dp[sum/2];
    }
};